/*
 * 4.2
 * Given a directed graph, design an algorithm to find out whether there is a route be-
 * tween two nodes.
 */
#include <stdio.h>
#include <string.h>

const int V[] = { 1, 2, 6, 7, 9 };
const int E[][2] = { { 1, 2 }, { 1, 6 }, { 6, 7 }, { 7, 9 } };
const int size = sizeof(E)/sizeof(E[0]);

bool route(int from, int to, int *routes, int curr)
{
    if (from == to) {
        return true;
    }
    for (int i = 0; i < size; i++) {
        if (E[i][0] == from) {
            /* loop? */
            bool loop = false;
            for (int j = 0; j < curr; j++) {
                if (routes[j] == i) {
                    loop = true;
                    break;
                }
            }
            if (!loop) {
                routes[curr++] = i;
                if (route(E[i][1], to, routes, curr)) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int routes[10];
    memset(routes, -1, sizeof(routes));
    bool b = route(2, 9, routes, 0);
    printf("route? %d\n", b);
    memset(routes, -1, sizeof(routes));
    b = route(1, 9, routes, 0);
    if (b) {
        printf("%d", E[routes[0]][0]);
        for (int i = 0; routes[i] >= 0; i++) {
            printf(" %d", E[routes[i]][1]);
        }
        printf("\n");
    }
    return 0;
}
